/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30



␈↓ α∧␈↓α␈↓ ¬KANOTHER SAMEFRINGE

␈↓ α∧␈↓␈↓ αTThis SAMEFRINGE is simpler than those in the last two ␈↓↓Newsletter␈↓s:

␈↓ α∧␈↓(DE SAMEFRINGE (X Y)
␈↓ α∧␈↓       (OR (EQ X Y)
␈↓ α∧␈↓           (AND (NOT (ATOM X))
␈↓ α∧␈↓                (NOT (ATOM Y))
␈↓ α∧␈↓                (SAME (GOPHER X) (GOPHER Y)))))

␈↓ α∧␈↓(DE SAME (X Y)
␈↓ α∧␈↓       (AND (EQ (CAR X) (CAR Y))
␈↓ α∧␈↓            (SAMEFRINGE (CDR X) (CDR Y))))

␈↓ α∧␈↓(DE GOPHER (U)
␈↓ α∧␈↓       (COND ((ATOM (CAR U)) U)
␈↓ α∧␈↓             (T (GOPHER (CONS (CAAR U) (CONS (CDAR U) (CDR U)))))))

␈↓ α∧␈↓Here it is in a proposed LISP publication language:

␈↓ α∧␈↓␈↓↓samefringe[x, y] ← x ␈↓αeq ␈↓↓y ∨ [¬␈↓αat ␈↓↓x ∧ ¬␈↓αat ␈↓↓y ∧ same[gopher x, gopher y]]

␈↓ α∧␈↓↓same[x, y] ← ␈↓αa ␈↓↓x ␈↓αeq a y ∧ ␈↓↓samefringe[␈↓αd ␈↓↓ x, ␈↓αd ␈↓↓y]

␈↓ α∧␈↓↓gopher u ← ␈↓αif at a ␈↓↓u ␈↓αthen␈↓↓ u ␈↓αelse␈↓↓ gopher ␈↓αaa ␈↓↓u . [␈↓αda ␈↓↓u . ␈↓αd ␈↓↓u] ␈↓

␈↓ α∧␈↓␈↓ αT␈↓↓gopher␈↓␈αdigs␈α
up␈αthe␈α
first␈αatom␈α
in␈αan␈α
S-expression,␈αpiling␈α
up␈αthe␈α
␈↓↓cdr␈↓␈αparts␈α
(with␈αits␈αhind␈α
legs)
␈↓ α∧␈↓so␈αthat␈αindexing␈αthrough␈αthe␈αatoms␈αcan␈αbe␈αresumed.␈α Because␈αof␈αshared␈αstructure,␈αthe␈αnumber␈αof
␈↓ α∧␈↓new␈α∩cells␈α∩in␈α∩use␈α∩in␈α∪each␈α∩argument␈α∩at␈α∩any␈α∩time␈α∪(apart␈α∩from␈α∩those␈α∩occupied␈α∩by␈α∪the␈α∩original
␈↓ α∧␈↓expression␈αand␈αassuming␈αiterative␈αexecution)␈αis␈αthe␈αnumber␈α
of␈α␈↓↓car␈↓s␈αrequired␈αto␈αgo␈αfrom␈αthe␈αtop␈α
to
␈↓ α∧␈↓the␈α∞current␈α∞atom␈α∞-␈α∞usually␈α∞a␈α∞small␈α∞fraction␈α∞of␈α∞the␈α∞size␈α∞of␈α∞the␈α∞S-expression.␈α∞ If␈α∞an␈α∞argument␈α∞of
␈↓ α∧␈↓␈↓↓samefringe␈↓ is not elsewhere referenced, its top level is forgotten and subject to garbage collection.

␈↓ α∧␈↓␈↓ αTA␈α
␈↓↓samefringe␈↓␈α
using␈α
even␈α
less␈α
storage␈α
can␈α
be␈α
based␈α
on␈α
the␈α
function␈α
␈↓↓residue[x,y]␈↓␈αthat␈α
matches
␈↓ α∧␈↓the successive atoms of ␈↓↓x␈↓ and ␈↓↓y and␈↓ whose value gives the left-over atoms if there are any:

␈↓ α∧␈↓␈↓↓residue[x, y] ←
␈↓ α∧␈↓↓␈↓ αT␈↓αif␈↓↓ x ␈↓αeq␈↓↓ y ␈↓αthen␈↓↓ ␈↓T␈↓↓
␈↓ α∧␈↓↓␈↓ αT␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αat␈↓↓ x ∧ ␈↓αat␈↓↓ y ␈↓αthen␈↓↓ ␈↓F␈↓↓
␈↓ α∧␈↓↓␈↓ αT␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αat␈↓↓ x ␈↓αthen␈↓↓ {gopher y}[λw.␈↓αif␈↓↓ x ␈↓αeq␈↓↓ ␈↓αa␈↓↓ w ␈↓αthen␈↓↓ ␈↓R␈↓↓ . ␈↓αd␈↓↓ w ␈↓αelse␈↓↓ ␈↓F␈↓↓]
␈↓ α∧␈↓↓␈↓ αT␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αat␈↓↓ y ␈↓αthen␈↓↓ {gopher x}[λw.␈↓αif␈↓↓ y ␈↓αeq␈↓↓ ␈↓αa␈↓↓ w ␈↓αthen␈↓↓ ␈↓L␈↓↓ . ␈↓αd␈↓↓ w ␈↓αelse␈↓↓ ␈↓F␈↓↓]
␈↓ α∧␈↓↓␈↓ αT␈↓αelse␈↓↓ {residue[␈↓αa␈↓↓ x,␈↓αa␈↓↓ y]}[λw.
␈↓ α∧␈↓↓                ␈↓αif␈↓↓ w ␈↓αeq␈↓↓ ␈↓F␈↓↓ ␈↓αthen␈↓↓ ␈↓F␈↓↓
␈↓ α∧␈↓↓                ␈↓αelse␈↓↓ residue[␈↓αif␈↓↓ ␈↓αa␈↓↓ w ␈↓αeq␈↓↓ ␈↓L␈↓↓ ␈↓αthen␈↓↓ ␈↓αd␈↓↓ w . ␈↓αd␈↓↓ x ␈↓αelse␈↓↓ ␈↓αd␈↓↓ x,␈↓αif␈↓↓ ␈↓αa␈↓↓ w ␈↓αeq␈↓↓ ␈↓R␈↓↓ ␈↓αthen␈↓↓ ␈↓αd␈↓↓ w . ␈↓αd␈↓↓ y ␈↓αelse␈↓↓ ␈↓αd␈↓↓ y]]␈↓,

␈↓ α∧␈↓where␈α
we␈α
put␈α
curly␈α
brackets␈α
around␈α
the␈α
arguments␈αof␈α
a␈α
function␈α
when␈α
we␈α
think␈α
it␈α
is␈α
clearer␈αto␈α
put
␈↓ α∧␈↓the␈αarguments␈αbefore␈αthe␈αfunction.␈α Thus␈α␈↓↓{x}f␈↓␈αis␈αanother␈αway␈αof␈αwriting␈α␈↓↓f[x]␈↓.␈α It␈αis␈αa␈αbit␈αawkward


␈↓ α∧␈↓␈↓ ε|1␈↓ ∧



␈↓ α∧␈↓to␈α
state␈αexactly␈α
how␈αmuch␈α
storage␈α
␈↓↓residue␈↓␈αuses.␈α
 This␈αmay␈α
be␈α
the␈αsame␈α
as␈αthe␈α
first␈αalgorithm␈α
given
␈↓ α∧␈↓by Finin and Rutter, but I found theirs hard to read, and these use no language extensions.

␈↓ α∧␈↓␈↓ αTI␈αthink␈αall␈αthis␈αshows␈αthat␈α␈↓↓samefringe␈↓␈αis␈αnot␈αan␈αexample␈αof␈αthe␈αneed␈αfor␈αco-routines,␈αand␈αa
␈↓ α∧␈↓new␈α"simplest␈αexample"␈αshould␈αbe␈αfound.␈α There␈αis␈αno␈αmerit␈αin␈αmerely␈αmoving␈α
information␈αfrom
␈↓ α∧␈↓data␈α⊂structure␈α⊂to␈α⊃control␈α⊂structure,␈α⊂and␈α⊃it␈α⊂makes␈α⊂some␈α⊂kinds␈α⊃of␈α⊂modification␈α⊂harder.␈α⊃ Thus␈α⊂a
␈↓ α∧␈↓game-playing␈α∂algorithm␈α∂that␈α⊂chooses␈α∂the␈α∂most␈α⊂"cost-effective"␈α∂node␈α∂of␈α⊂the␈α∂tree␈α∂to␈α⊂extend␈α∂can't
␈↓ α∧␈↓have␈α
the␈α
usual␈α
simple␈α
recursive␈α
structure.␈α
 A␈αprogram␈α
with␈α
only␈α
assignments␈α
and␈α
␈↓αgo␈α
to␈↓s␈αmay␈α
have
␈↓ α∧␈↓the␈α∞most␈α∞easily␈α∞modified␈α∞control␈α∞structure.␈α∞ Of␈α∞course,␈α∞elegance,␈α∞understandability␈α∞and␈α∞a␈α
control
␈↓ α∧␈↓logic admitting straightforward proofs of correctness are also virtues.

␈↓ α∧␈↓John McCarthy
␈↓ α∧␈↓Artificial Intelligence Laboratory
␈↓ α∧␈↓Computer Science Department
␈↓ α∧␈↓Stanford University
␈↓ α∧␈↓Stanford, California 94305

␈↓ α∧␈↓ARPANET: MCCARTHY@SU-AI

␈↓ α∧␈↓␈↓εThis draft of SAMEFR[F76,JMC]@SU-AI PUBbed at 12:04 on January 21, 1977.␈↓





























␈↓ α∧␈↓␈↓ ε|2␈↓ ∧